#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

// 安全计算long long的平方根（解决sqrt不支持long long的问题）
// 返回值：sqrt(x)的整数部分（向下取整）
long long safe_sqrt(long long x) {
    if (x < 0) return 0;  // 异常处理：负数无实数平方根
    // 1. 类型转换：long long -> double（注意：大整数可能丢失精度，但常规分解场景足够）
    double sqrt_val = sqrt((float)x);
    // 2. 转换为long long，同时验证是否因精度问题偏小（避免漏判完全平方数）
    long long b = (long long)sqrt_val;
    // 3. 修正：若(b+1)^2 == x，说明精度不足导致b偏小，需+1
    if ((b + 1) * (b + 1) == x) {
        b++;
    }
    return b;
}

// 费马分解：对奇数x进行分解，返回(p, q)，满足x = p*q
void fermat(long long x, long long *p, long long *q) {
    long long a = ceil(sqrt(x));  // 向上取整，对应Python的math.ceil
    long long b2 = a * a - x;
    long long b = round(sqrt(b2));  // 四舍五入，对应Python的math.round

    // 循环直到b² == b2（找到完全平方数）
    while (b * b != b2) {
        a += 1;
        b2 = a * a - x;
        b = round(sqrt(b2));
    }

    // 计算并返回因子 p = a - b, q = a + b
    *p = a - b;
    *q = a + b;
    printf("%lld %lld %lld\n", a, b, x);  // 复刻Python的打印逻辑
}

//  factorization：递归分解n为质因子（用栈模拟Python的列表栈）
void factorization(long long n) {
    long long *stack = (long long *)malloc(100 * sizeof(long long));  // 栈缓冲区（足够存储大整数因子）
    int top = 0;  // 栈顶指针（初始化空栈）
    stack[top++] = n;  // 初始值入栈

    // 遍历栈，分解所有因子
    while (top > 0) {
        long long x = stack[--top];  // 出栈（对应Python的pop()）

        if (x == 2) {  // 2是质数，直接加入结果（头部插入，保持升序）
            printf("%lld ", x);
            continue;
        }

        long long p, q;
        if (x & 1) {  // 奇数：用费马分解
            fermat(x, &p, &q);
        } else {  // 偶数：直接分解为2和x/2
            p = 2;
            q = x / 2;
        }

        if (p == 1) {  // p=1时，q是质数，加入结果
            printf("%lld ", q);
        } else {  // 非质数，继续入栈分解（先入q再入p，保证出栈顺序正确）
            stack[top++] = q;
            stack[top++] = p;
        }
    }
    printf("\n");
    free(stack);  // 释放栈内存
}

int main() {
    // 测试用例：与Python一致，分解200
    factorization(200);  // 输出：2 2 2 5 5
    return 0;
}